8927. Smallest divisor

For a given positive integer n, find and print its smallest divisor greater than 1.

Input. One positive integer n (1 < n < 2³¹).

Output. Print the smallest divisor of n greater than 1.

Sample input	Sample output
21	3

SOLUTION

number theory

Algorithm analysis

Iterate through all possible divisors of n in the range from 2 to inclusive and find the smallest one. If no divisors are found in the interval [2; ], the answer will be the number n itself.

Example

If n = 21, the smallest divisor is 3.

If n = 13 (a prime number), the smallest divisor is 13.

Algorithm implementation

Read the input value of n.

scanf("%d", &n);

Initialize flag = 0. Iterate through the possible divisors of n in the range from 2 to inclusive. Upon finding the first (smallest) divisor, set flag = 1, print the found divisor, and terminate the loop.

flag = 0;

for (i = 2; i <= sqrt(n); i++)

if (n % i == 0)

{

printf("%d\n", i);

flag = 1;

break;

}

If no divisor is found, the number n is prime. In this case, print the number n itself.

if (flag == 0) printf("%d\n", n);

Java implementation

import java.util.*;

class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int flag = 0;

for (int i = 2; i <= Math.sqrt(n); i++)

if (n % i == 0)

{

System.out.println(i);

flag = 1;

break;

}

if (flag == 0) System.out.println(n);

con.close();

}

}

Python implementation

import math

Read the input value of n.

n = int(input())

Iterate through the possible divisors of n in the range from 2 to inclusive. Upon finding the first (smallest) divisor, print it and terminate the loop.

for i in range(2, math.isqrt(n)+1):

if n % i == 0:

print(i)

break

If the loop terminates naturally (without using break), the else block is executed.

If no divisor is found, the number n is prime. Print the number n itself.

else: # we are here when the loop terminates by itself

print(n)